package com.agile.leetcode.array.binarySearch;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * 示例 1:
 * <p>
 * 输入: [0,1,3]
 * 输出: 2
 * <p>
 * 示例 2:
 * <p>
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *
 * @Author ChenZhangKun
 * @Date 2020/11/25 15:19
 */
public class BianrySearch {
    public static void main(String[] args) {
        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 9};
        System.out.println(getMissedNum(array));
    }

    public static Integer getMissedNum(int[] array) {
        // 拿到数组长度
        int length = array.length;
        int i = 0;
        while (i <= length) {
            int j = (length + i) / 2;
            if (array[j] == j) i = j + 1;
            else length = j - 1;
        }
        return i;
    }
}
